|
In graph theory, a friendly-index set is a finite set of integers associated with a given undirected graph and generated by a type of graph labeling called a friendly labeling. A friendly labeling of an -vertex undirected graph is defined to be an assignment of the values 0 and 1 to the vertices of with the property that the number of vertices labeled 0 is as close as possible to the number of vertices labeled 1: they should either be equal (for graphs with an even number of vertices) or differ by one (for graphs with an odd number of vertices). Given a friendly labeling of the vertices of , one may also label the edges: a given edge is labeled with a 0 if its endpoints and have equal labels, and it is labeled with a 1 if its endpoints have different labels. The friendly index of the labeling is the absolute value of the difference between the number of edges labeled 0 and the number of edges labeled 1. The friendly index set of , denoted , is the set of numbers that can arise as friendly indexes of friendly labelings of . The Dynamic Survey of Graph Labeling contains a list of papers that examines the friendly indices of various graphs. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Friendly-index set」の詳細全文を読む スポンサード リンク
|